package leetcodesolution;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-06
 * Time: 16:36
 */
//判断两个树是否相同
    //时间复杂度: O min(n,m)
    //m, n 分别为两个树的个数
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
public class Solution2 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //一个空，一个不为空，不相同
        if((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        //走完上面的代码后，要么两个树都不为空，要么两个树都为空
        //判断两个节点是不是空,都为空就是相同的
        if(p == null && q == null) {
            return true;
        }

        //剩下的就是都不为空了，判断其中的值
        if(p.val != q.val) {
            //两个树的值不相同
            return false;
        }
        //两个树都不为空，且两个树的值都相同，那么就要开始比较他们的左右子树是否相同了
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
